package com.zwd.cases.algorithm;

import java.util.Arrays;

/**
 * @Description 冒泡排序
 * 冒泡排序算法的运作如下：
 *  比较两个相邻的数，如果前面的数大于后面的数，则将这两个数交换位置。第一次遍历后，最大的数会被放到数组的最后位置，即array[length - 1]。
 *  第二次遍历时跳过最后一个元素，因为该元素通过第一次遍历已经确定是最大值。
 *  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
 *
 * @Author zhengwd
 * @Date 2022/8/1 13:56
 **/
public class BubbleSort {

    public static void main(String[] args) {
        // 测试数据
        int[] array = {19, 15, 37, 12};
        // 冒泡排序
        bubbleSort(array);
        // 遍历输出
        Arrays.stream(array).forEach(System.out::println);
    }

    /**
     * 冒泡算法-版本1
     * @param array 数据集合
     */
    private static void bubbleSort(int[] array) {
        // 判空
        if (array == null || array.length == 0) {
            return;
        }
        // 数据处理
        int length = array.length;
        for (int i = 0; i < length-1; i++) {
            for (int j = 0; j < length-1-i; j++) {
                if (array[j] > array[j+1]) {
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }

    /**
     * 冒泡算法-版本2-如果array数组本来就是有序的，则第一次循环结束后由于没有元素交换
     * @param array 数据集合
     */
    private static void bubbleSort2(int[] array) {
        // 判空
        if (array == null || array.length == 0) {
            return;
        }
        // 数据处理
        int length = array.length;
        for (int i = 0; i < length-1; i++) {
            // 当次循环是否发生元素交换
            boolean isSwap = false;
            for (int j = 0; j < length-1-i; j++) {
                if (array[j] > array[j+1]) {
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
            // 如果当次循环没有发生元素交换, 则数组已经排好序
            if (!isSwap) {
                return;
            }
        }
    }
}
